package personal_exercise;

import java.util.*;
import java.io.*;

public class Demo1 {


    // 重排字符串
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        char[] s = in.next().toCharArray();

        // 1. 计算各个字母出现的次数并找到出现次数最多的字符
        int[] count = new int[26];
        int max = 0;
        char maxChar = 0;
        for (int i = 0; i < n; i++) {
            char ch = s[i];
            if (++count[ch - 'a'] > max) {
                max = count[ch - 'a'];
                maxChar = ch;
            }
        }
        // 如果 max > (n + 1) / 2,则说明一定不能重排
        if (max > (n + 1) / 2) {
            System.out.println("no");
            return;
        }


        // 2. 先对出现次数最多的字母进行重排
        char[] arr = new char[n];
        int k = 0;
        for (; max-- > 0; k += 2) {
            arr[k] = maxChar;
            count[maxChar - 'a']--;
        }

        // 3. 对剩下位置进行重排
        for (int i = 0; i < 26; i++) {
            if (count[i] == 0) continue;

            while (count[i]-- > 0) {
                if (k >= n) k = 1;
                arr[k] = (char)('a' + i);
                k += 2;
            }
        }
        System.out.println("yes");
        System.out.println(new String(arr));
    }


    // mari和shiny
    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String str = in.next();

        long s = 0, sh = 0, shy = 0;
        if (str.charAt(0) == 's') s = 1;

        for (int i = 1; i < n; i++) {
            char ch = str.charAt(i);
            if (ch == 's') s++;
            else if (ch == 'h') sh += s;
            else if (ch == 'y') shy += sh;
        }

        System.out.println(shy);
    }



    // 游游的水果大礼包
    public static void main3(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        int a = in.nextInt(), b = in.nextInt();

        // res = x * a + y * b。 x、y分别为一和二号礼包的数量
        long res = 0;
        for (int x = 0; x <= Math.min(n / 2, m); x++) {
            int y = Math.min(n - 2 * x, (m - x) / 2);
            long profit = (long)x * a + (long)y * b;
            if (profit > res) res = profit;
        }

        System.out.println(res);
    }


    // 组队竞赛 (https://www.nowcoder.com/questionTerminal/6736cc3ffd1444a4a0057dee89be789b)
    public static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    public static Read in = new Read();
    public static void main4(String[] args) throws IOException {
        int n = in.nextInt();
        int[] scores = new int[n * 3];
        for (int i = 0;i < n * 3; i++) scores[i] = in.nextInt();

        Arrays.sort(scores);
        long res = 0;
        for (int i = n * 3 - 2, count = n; count-- > 0; i -= 2) {
            res += scores[i];
        }
        out.println(res);
        out.close();
    }


    // DP25 删除相邻数字的最大分数 (https://www.nowcoder.com/practice/3bcf72c738b6494bbe1ebe0ffde56152?tpId=230&tqId=40419&ru=/exam/oj)
    public static void main5(String[] args) throws IOException{
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = in.nextInt();

        // 1. 先统计相同元素的总和
        int[] sum = new int[10001];
        for (int x : arr) sum[x] += x;

        // f[i]: 以 下标i 为结尾且选择 元素i的所能获得的最大分数
        // g[i]: 以 下标i 为结尾且不选择 元素i的所能获得的最大分数
        int[] f = new int[10001], g = new int[10001];
        for (int i = 1; i <= 10000; i++) {
            f[i] = g[i - 1] + sum[i];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }
        System.out.println(Math.max(g[10000], f[10000]));
    }


    // 分组 (https://ac.nowcoder.com/acm/problem/229023)
    public static void main6(String[] args) throws IOException {
        int n = in.nextInt(), m = in.nextInt(), max = 0;
        int[] arr = new int[n], count = new int[n + 1];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
            // 1. 统计每个声部的学生人数
            count[arr[i]]++;
            max = Math.max(max, count[arr[i]]);
        }

        // 2. 枚举:固定人数最多的组,查看是否符合分组要求
        int left = 1, right = max, mid = 0;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (isValid(mid, count, m)) right = mid;
            else left = mid + 1;
        }

        if (isValid(left, count, m)) {
            System.out.println(left);
        } else {
            System.out.println(-1);
        }
        out.close();
    }
    private static boolean isValid(int i, int[] count,int m) {
        int sum = 0;
        for (int j = 1; j < count.length; j++) {
            if (count[j] > 0) {
                int x = count[j] / i;
                sum += count[j] % i == 0 ? x : x + 1;
            }
        }
        return sum <= m;
    }
//    public static void main6(String[] args) throws IOException {
//        int n = in.nextInt(), m = in.nextInt(), max = 0;
//        int[] arr = new int[n], count = new int[n + 1];
//        for (int i = 0; i < n; i++) {
//            arr[i] = in.nextInt();
//            // 1. 统计每个声部的学生人数
//            count[arr[i]]++;
//            max = Math.max(max, count[arr[i]]);
//        }
//
//        // 2. 枚举:固定人数最多的组,查看是否符合分组要求
//        for (int i = 1; i <= max; i++) {
//            int sum = 0;
//            for (int j = 1; j <= n; j++) {
//                if (count[j] > 0) {
//                    int x = count[j] / i;
//                    sum += count[j] % i == 0 ? x : x + 1;
//                }
//            }
//            if (sum <= m) {
//                System.out.println(i);
//                out.close();
//                return;
//            }
//        }
//        System.out.println(-1);
//        out.close();
//    }



    //  HJ63 DNA序列
    public static void main7(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        int k = in.nextInt();
        int left = 0, right = 0, sum = 0;
        int resIndex = 0, max = 0;
        for (; right < s.length(); right++) {
            if (s.charAt(right) == 'C' || s.charAt(right) == 'G') sum++;

            if (right - left + 1 == k) {
                if (sum > max) {
                    resIndex = left;
                    max = sum;
                }
                if (s.charAt(left) == 'C' || (s.charAt(left) == 'G')) sum--;
                left++;
            }
        }

        System.out.println(s.substring(resIndex, resIndex + k));
    }



    // 神奇数 (https://www.nowcoder.com/questionTerminal/99fa7be28d5f4a9d9aa3c98a6a5b559a)
    public static void main8(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt(), b = in.nextInt();

        int res = 0;
        while (a <= b) {
            // 1. 获取该数字的各个位上的数字
            int[] arr = getNums(a++);

            // 2. 依次枚举,验证每两个数组成的数字是否为神奇数
            for (int i = 0, n = arr.length; i < n; i++) {
                boolean flag = false;
                for (int j = 0; j < n; j++) {
                    if (i == j || arr[i] == 0) continue;
                    int num = arr[i] * 10 + arr[j];
                    if (isPrimeNum(num)) {
                        res++;
                        flag = true;
                        break;
                    }
                }
                if (flag) break;
            }
        }

        System.out.println(res);
    }
    private static int[] getNums(int num) {
        String s = Integer.toString(num);
        int[] arr = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            arr[i] = s.charAt(i) - '0';
        }
        return arr;
    }
    private static boolean isPrimeNum(int num) {
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) return false;
        }
        return true;
    }




    // 非对称之美 (https://ac.nowcoder.com/acm/problem/214851)
    public static void main9(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();

        char ch = s.charAt(0);
        boolean b = true, flag = true;
        for (int left = 0, right = s.length() - 1; left <= right; left++, right--) {
            if (s.charAt(left) != s.charAt(right)) {
                b = false;
                break;
            }
            if (ch != s.charAt(left)) flag = false;
        }

        if (!b) {
            System.out.println(s.length());
        } else {
            if (flag) System.out.println(0);
            else System.out.println(s.length() - 1);
        }
    }



    // 数组变换(https://www.nowcoder.com/questionTerminal/c55f4f15cc3f4ff0adede7f9c69fa0c1)
    public static void main10(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }

        int max = -1;
        for (int x : arr) {
            if (x > max) max = x;
        }

        for (int x : arr) {
            if (x == max) continue;
            if (max % x != 0) {
                System.out.println("NO");
                return;
            }
            int num = max / x;
            if ((num & (num - 1)) != 0) {
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
    }



    // 打怪
    public static void main11(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();

        while (t-- > 0) {
            int h = in.nextInt(), a = in.nextInt(), H = in.nextInt(), A = in.nextInt();
            if (a >= H) {
                System.out.println(-1);
                continue;
            }

            int x = H / a + (H % a == 0 ? 0 : 1);
            int res = h / ((x- 1) * A);
            if (h % ((x- 1) * A) == 0) res--;
            System.out.println(res);
        }
    }



    // 字符串分类
    public static void main12(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        Set<String> hash = new HashSet<>();

        while (n-- > 0) {
            char[] arr = in.next().toCharArray();
            Arrays.sort(arr);
            hash.add(new String(arr));
        }
        System.out.println(hash.size());
    }


    // NC345 城市群数量 (floodFill 算法)
    private boolean[]  vis;
    private int n;
    public int citys (List<List<Integer>> m) {
        // dfs: 深度优先遍历图
        n = m.size();
        vis = new boolean[n];
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (m.get(i).get(j) == 1 && !vis[j]) {
                    dfs(j, m);
                    res++;
                }
            }
        }
        return res;
    }
    private void dfs(int i, List<List<Integer>> m) {
        vis[i] = true;

        for (int j = 0; j < n; j++) {
            if (m.get(i).get(j) == 1 && !vis[j]) {
                dfs(j, m);
            }
        }
    }



    // BC145 [NOIP2008]笨小猴
    public static void main13(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] arr = in.next().toCharArray();

        int[] hash = new int[26];
        for (char ch : arr) {
            hash[ch - 'a']++;
        }

        int maxn = 0, minn = 1000;
        for (int x : hash) {
            if (x == 0) continue;
            if (x > maxn) maxn = x;
            if (x < minn) minn = x;
        }
        if (maxn == minn) {
            System.out.println("No Answer");
            System.out.println(0);
            return;
        }

        if (isPrimeNum(maxn - minn)) {
            System.out.println("Lucky Word");
            System.out.println(maxn - minn);
        } else {
            System.out.println("No Answer");
            System.out.println(0);
        }
    }
//    private static boolean isPrimeNum(int n) {
//        if (n < 2) return false;
//        for (int i = 2; i <= Math.sqrt(n); i++) {
//            if (n % i == 0) return false;
//        }
//        return true;
//    }

    // NC383 主持人调度（一）
    public boolean hostschedule (ArrayList<ArrayList<Integer>> schedule) {
        schedule.sort((a, b) -> a.get(0) - b.get(0));
        PriorityQueue<ArrayList<Integer>> pq = new PriorityQueue<>((a, b) -> b.get(1) - a.get(1));
        for (ArrayList<Integer> list: schedule) {
            if (!pq.isEmpty()) {
                if (pq.peek().get(1) > list.get(0)) return false;
                else pq.poll();
            }
            pq.offer(list);
        }
        return true;
    }


    // 小红的ABC
    public static void main14(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] s = in.next().toCharArray();

        int res = -1;
        for (int i = 0, n = s.length; i < n - 1; i++) {
            if (s[i] == s[i + 1]) {
                System.out.println(2);
                return;
            } else if (i + 2 < n && s[i] == s[i + 2]){
                res = 3;
            }
        }
        System.out.println(res);
    }



    //  空调遥控
    public static void main15(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), p = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }

        // 解法一: 排序 + 滑动窗口
        // 1. 排序
        Arrays.sort(arr);
        // 2. 滑动窗口
        int res = 0;
        int left = 0, right = 0;
        for ( ; right < n; right++) {
            while (arr[right] - arr[left] > 2 * p) {
                left++;
            }
            res = Math.max(res, right - left + 1);
        }
        System.out.println(res);
    }
//    public static void main15(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int n = in.nextInt(), p = in.nextInt();
//        int[] arr = new int[n];
//        for (int i = 0; i < n; i++) {
//            arr[i] = in.nextInt();
//        }
//
//        // 解法一: 排序 + 二分
//        // 1. 排序
//        Arrays.sort(arr);
//        // 2. 枚举室内温度 K
//        int res = 0;
//        for (int i = arr[0]; i <= arr[n - 1]; i++) {
//            int lValue = Math.max(1, i - p);
//            int rValue = Math.min(1000000, i + p);
//            // 3. 二分查找左端点和右端点
//            int left = 0, right = n - 1, mid = 0;
//            while (left < right) {
//                mid = left + (right - left) / 2;
//                if (arr[mid] < lValue) left = mid + 1;
//                else right = mid;
//            }
//            int start = left;
//            for (left = 0, right = n - 1; left < right; ) {
//                mid = left + (right - left + 1) / 2;
//                if (arr[mid] > rValue) right = mid - 1;
//                else left = mid;
//            }
//            res = Math.max(res, left - start + 1);
//        }
//        System.out.println(res);
//    }



    // NC147 主持人调度（二）
    public int minmumNumberOfHost (int n, int[][] startEnd) {
        Arrays.sort(startEnd, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(startEnd[0][1]);
        for (int i = 1; i < n; i++) {
            int[] arr = startEnd[i];
            if (!pq.isEmpty() && pq.peek() <= arr[0]) {
                pq.poll();
            }
            pq.offer(arr[1]);
        }
        return pq.size();
    }

}



class Read { // 自定义快速读入
    StringTokenizer st = new StringTokenizer("");
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    String next() throws IOException {
        while (!st.hasMoreTokens()) {
            st = new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }

    String nextLine() throws IOException {
        return bf.readLine();
    }

    int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

}